import { Node } from './Node'
import { btPrint } from 'hy-algokit'


class bsTree {
    root: Node<number> | null = null;


    // 打印二叉树
    print() {
        btPrint(this.root);
    }
    // 插入节点
    insert(value: number) {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    // 递归插入节点
    insertNode(node: Node<number>, newNode: Node<number>) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode
            } else {
                this.insertNode(node.left, newNode)
            }
        } else {
            if (node.right === null) {
                node.right = newNode
            } else {
                this.insertNode(node.right, newNode)
            }
        }
    }

    // 查找节点
    search(value: number): boolean {
        let current = this.root;
        while (current) {
            if (value === current.value) {
                return true
            }
            else if (value < current.value) {
                current = current.left
            } else {
                current = current.right
            }
        }
        return false
    }

    // 最小值
    minValueNode(): number | undefined {
        let current = this.root;
        if (current === null) {
            return undefined
        }
        while (current.left) {
            current = current.left
        }
        return current.value
    }

    // 最大值
    maxValueNode(): number | undefined {
        let current = this.root;
        if (current === null) {
            return undefined
        }
        while (current.right) {
            current = current.right
        }
        return current.value
    }

    // 先序遍历
    preOrderTraversal(node?: Node<number> | null | undefined) {
        if (node === undefined) {
            node = this.root
        }
        if (node === null) {
            return
        }
        console.log(node.value);
        
        if (node.left) {
            this.preOrderTraversal(node.left)
        }
        if (node.right) {
            this.preOrderTraversal(node.right)

        }
    }

    // 中序遍历
    inOrderTraversal(node?: Node<number> | null | undefined) {
        if (node === undefined) {
            node = this.root
        }
        if(node === null){
            return
        }
        if(node.left){
            this.inOrderTraversal(node.left)
        }
        console.log(node.value);
        if(node.right){
            this.inOrderTraversal(node.right)
        }
    }

    // 后续遍历
    postOrderTraversal(node?:Node<number> | null | undefined){
        if (node === undefined) {
            node = this.root
        }
        if(node === null){
            return
        }
        if(node.left){
            this.postOrderTraversal(node.left)
        }
        if(node.right){
            this.postOrderTraversal(node.right)
        }
        console.log(node.value);
    }

    // 删除 
    remove(value: number): boolean {
        // 无节点
        if(this.root === null){
            return false
        }
        // 删除的是根节点
        if(value == this.root?.value){
            this.root = null
            return true
        }
        // 查找节点
        let current = this.root;
        let parantNode = null;
        while(current.value !== value){
          
            parantNode = current

            if(value < current.value){
                current = current.left!
            }else if(value > current.value){
                current = current.right!
            }
              if(current === null){
                return false
            }
        }
        console.log('找到要删除的节点', current);
        console.log('父节点', parantNode);
        

        
        if(current.left === null && current.right === null){
            // 删除的是叶子结点
            if(parantNode!.left!.value === current.value){
                parantNode!.left = null
            }else if(parantNode!.right!.value === current.value){
                parantNode!.right = null
            }
        }else if(current.left !== null && current.right === null){
            // 删除的节点有一个左子树
            parantNode!.left = current.left
            current.left = null
        }else if(current.right !== null && current.left === null){
            // 删除的节点有一个右子树
            parantNode!.right = current.right
            current.right = null

        }else if(current.left !== null && current.right !== null){
            // 删除的节点有两个子树,用后驱节点替换
            const successNodeParent = this.getSuccessNode(current)!
            const successNode = successNodeParent!.left!

            // 后驱节点的父节点是当前节点,
            if(successNodeParent!.value === current.value){
                // current没什么用先保存一下successNode的右子树
                current.left = successNode.right
                successNode.right = null
            // 判断父节点左边删东西还是右边删东西
            if(parantNode!.right!.value === current.value){
                // 对应位置把指向换成我们的右驱节点
                parantNode!.right = successNode
            }
            if(parantNode!.left!.value === current.value){
                parantNode!.left = successNode
            }
            // 右驱节点有可能有右子树，上两步已经放到current的左子树上，这里不把东西送给successNode就完成了
                successNode.left = current.left
                successNode.right = current.right
                current.left = null
                current.right = null
                return true
            }

            // 其他情况，右驱父节点跟删除的不一样
            if(parantNode!.right!.value === current.value){
                // 右驱的父节点左子树换成右驱的右子树，完成下方的节点替换
                successNodeParent!.left = successNode.right
                // 上方父节点替换右驱动，有驱动的左右子树用删除节点的左子树，完成狸猫换太子
                parantNode!.right = successNode
                successNode.left = current.left
                successNode.right = current.right
                current.left = null
                current.right = null
                return true
            }
            if(parantNode!.left!.value === current.value){
                successNodeParent!.left = successNode.right
                parantNode!.left = successNode
                successNode.left = current.left
                current.left = null
                successNode.right = current.right
                current.right = null
                return true

            }


        }
        return true
    }

    // 获取后驱节点的父节
    getSuccessNode(node:Node<number>){
        let current = node.right!
        let parantNode = node;
        while(current.left){
            parantNode = current
            current = current.left
        }
        return parantNode
    }
}


const bst = new bsTree();
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)

bst.print()

// console.log('查找15', bst.search(15));
// console.log('查找122', bst.search(122));

// console.log('最小值', bst.minValueNode());
// console.log('最大值', bst.maxValueNode());

// console.log('先序遍历');
// bst.preOrderTraversal()

// console.log('中序遍历');
// bst.inOrderTraversal()

// console.log('后续遍历');
// bst.postOrderTraversal()

// console.log('删除3');
// bst.remove(5)
// bst.print()

// console.log('删除12');
// bst.remove(12)
// bst.print()

console.log('删除13');
bst.remove(13)
bst.print()